/*************************************************
 *	文件名称：mydata.c
 *	文件说明：	程序实现的源码
				1.算法2.8 GetElem 在单链表中的实现
				2.算法2.9 ListInsert 在单链表中的实现
				3.算法2.10 ListDelete 在单链表中的实现
				4.算法2.11 CreateList_L 一个从表尾到表头逆向建立单链表的算法
				5.算法2.12 将两个有序链表合并为一个有序链表
 *	程序平台：for linux
 *	文件作者：Jason <jasonsunsoft@163.com>
 *	文件时间：2014年8月21日 21:00
*************************************************/
#include "mydata.h"


//算法2.13 在静态单链线性表S中查找一个值为e的元素
int LocateElem_SL(SLinkList S, ElemType e)
{
	int i;

	i = S[0].cur;					//i指示表中第一个节点
	while (i && S[i].data != e)		//在表中顺联查找
		i = S[i].cur;
	return i;
}//LocateElem_SL

//算法2.14 初始化空静态链表数组
void InitSpace_SL(SLinkList *space)
{
	int i ;
	for (i = 0; i < MAXSIZE - 1; ++i)
		(*space)[i].cur = i + 1;
		(*space)[MAXSIZE - 1].cur = 0;
}//InitSpace_SL

//算法2.15 静态链表的空间分配函数
int Malloc_SL(SLinkList *space)
{
	int i;
	i = (*space)[0].cur;
	if ((*space)[0].cur)
		(*space)[0].cur = (*space)[i].cur;
	return i;
}// Malloc_SL

//算法2.16 静态链表的空间释放函数
void Free_SL(SLinkList *space, int k)
{
	(*space)[k].cur = (*space)[0].cur;
	(*space)[0].cur = k;
}//Free_SL


//算法2.17 依次输入集合A和集合B的元素，在一维数组space中建立集合(A-B)∪(B-A)
void difference(SLinkList *space, int *S)
{
	int r, m, n, i, j, k, p;
	ElemType b;

	InitSpace_SL(space);		//初始化备用空间
	*S = Malloc_SL(space);		//生成S的头结点 S = 1
	r = *S;						//r指向S的当前最后节点
	scanf("%d %d", &m, &n);		//输入集合A 和 B的长度
	for (j = 1; j <= m; ++j)	//建立集合A的链表
	{
		i = Malloc_SL(space);			//分配空间
		scanf("%d", &(*space)[i].data);	//输入A的值
		(*space)[r].cur = i;			//将数据插入到表尾
		r = i;							//更新最后节点位置
	}
	(*space)[r].cur = 0;				//结尾的指针为空
	for (j = 1; j <= n; ++j)
	{
		scanf("%d",&b);					//输入B的值
		p = *S;							//将p指向链表S的头结点
		k = (*space)[*S].cur;			//将k指向链表A的第一个元素
		while (k != (*space)[r].cur && (*space)[k].data != b)	//循环继续的条件 k不是A的最后一个节点 && k指向的数据与b不相同
		{
			p = k;
			k = (*space)[k].cur;
		}
		if (k == (*space)[r].cur)	//查询到A链表的结尾，没有与b相同的数据，将b插入链表
		{
			i = Malloc_SL(space);
			(*space)[i].data = b;
			(*space)[i].cur = (*space)[r].cur;
			(*space)[r].cur = i;
		}
		else						//查找到与b相同的元素，删除该结点
		{
			(*space)[p].cur = (*space)[k].cur;
			Free_SL(space, k);
			if (r == k)
				r = p;
		}
	}
}//difference
